// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
#include <vector>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
using namespace std;
class Solution
{
public:
    string res1 = "";                      //全局变量，每种对应情况的字符串
    vector<string> res;                    //全局变量，最终要返回的vector
    void digui(string digits, string res1) //自己写的递归函数
    {
        if (digits == "") //最终退出递归的条件
        {
            res.push_back(res1); //这时候digits空了，我们把得到的res1存入vector中，退出递归
        }
        else //正常情况下，我们进入else这部分的处理
        {
            if (digits[0] == '2') //如果首位是2
            {
                digui(digits.substr(1, digits.size() - 1), res1 + "a"); //那么取digits的第二位开始一直到最后一位，res1加上“a”，进入递归
                digui(digits.substr(1, digits.size() - 1), res1 + "b"); //前一行的递归完成后，进入这一行的递归，digits这时候仍然是初始的digits，
                                                                        //我们同样要取第二位到最后一位的digits，res1仍然是初始的res1，同样要res1加上“b”
                digui(digits.substr(1, digits.size() - 1), res1 + "c"); //相同的处理
            }
            else if (digits[0] == '3') //如果首位是3，同样的处理
            {
                digui(digits.substr(1, digits.size() - 1), res1 + "d");
                digui(digits.substr(1, digits.size() - 1), res1 + "e");
                digui(digits.substr(1, digits.size() - 1), res1 + "f");
            }
            else if (digits[0] == '4')
            {
                digui(digits.substr(1, digits.size() - 1), res1 + "g");
                digui(digits.substr(1, digits.size() - 1), res1 + "h");
                digui(digits.substr(1, digits.size() - 1), res1 + "i");
            }
            else if (digits[0] == '5')
            {
                digui(digits.substr(1, digits.size() - 1), res1 + "j");
                digui(digits.substr(1, digits.size() - 1), res1 + "k");
                digui(digits.substr(1, digits.size() - 1), res1 + "l");
            }
            else if (digits[0] == '6')
            {
                digui(digits.substr(1, digits.size() - 1), res1 + "m");
                digui(digits.substr(1, digits.size() - 1), res1 + "n");
                digui(digits.substr(1, digits.size() - 1), res1 + "o");
            }
            else if (digits[0] == '7')
            {
                digui(digits.substr(1, digits.size() - 1), res1 + "p");
                digui(digits.substr(1, digits.size() - 1), res1 + "q");
                digui(digits.substr(1, digits.size() - 1), res1 + "r");
                digui(digits.substr(1, digits.size() - 1), res1 + "s");
            }
            else if (digits[0] == '8')
            {
                digui(digits.substr(1, digits.size() - 1), res1 + "t");
                digui(digits.substr(1, digits.size() - 1), res1 + "u");
                digui(digits.substr(1, digits.size() - 1), res1 + "v");
            }
            else if (digits[0] == '9')
            {
                digui(digits.substr(1, digits.size() - 1), res1 + "w");
                digui(digits.substr(1, digits.size() - 1), res1 + "x");
                digui(digits.substr(1, digits.size() - 1), res1 + "y");
                digui(digits.substr(1, digits.size() - 1), res1 + "z");
            }
        }
    }
    vector<string> letterCombinations(string digits)
    {
        if (digits == "") //边界情况处理，返回一个空的vector
            return res;
        digui(digits, res1); //进入递归处理，深度优先读取树
        return res;          //最终返回vector
    }
};
